//////////////////////////////////////////////////////////////////////////////////////////////////////
// 项目名   : Container
// 文件名   : TestForward_List.h
// 作者     : Aiye
// 日期     : 2025/9/4 21:04
// 邮箱     : 2878548868@qq.com
// 摘要     : 介绍单向链表
//////////////////////////////////////////////////////////////////////////////////////////////////////
#ifndef CONTAINER_TESTFORWARD_LIST_H
#define CONTAINER_TESTFORWARD_LIST_H
#include <forward_list>
#include <iostream>
#include <string>

#include "GlobalVariable.h"

/**
 * @brief 测试单向链表
 */
class TestForwardList
{
public:
    static void TestConstructor()
    {
        // 与list的几乎功能一致，但实现方法不同
        std::forward_list<int> nFlist1; // 默认构造函数，构造一个空的单向链表
        std::forward_list<int> nFlist2(3); // 构造一个包含3个元素的单向链表，元素值默认初始化（int为0）
        std::forward_list<int> nFlist3(3, 3); // 构造一个包含3个元素的单向链表，每个元素的值都为3
        auto nFlist4{nFlist3}; // 拷贝构造函数，深拷贝，不共享内存
        auto nFlist5{std::move(nFlist4)}; // 移动构造函数
        std::forward_list<int> nFlist6{1, 2, 3, 4}; // 初始化列表构造，推荐使用
        decltype(nFlist6)().swap(nFlist6); // 使用swap技巧清空并释放forward_list内存
    }

    static void TestAssign()
    {
        std::forward_list<std::string> strFlist1{"Hello String", "Hello Forward_List", "Hello Map"};
        auto strFlist2 = strFlist1; // 赋值拷贝，深拷贝，不共享内存
        auto strFlist3 = std::move(strFlist2); // 移动赋值拷贝
        std::forward_list<std::string> strFlist4{};
        strFlist4.assign(strFlist1.begin(), strFlist1.end()); // 使用迭代器范围赋值
        strFlist4.assign(3, "Hello"); // 赋值3个"Hello"字符串
    }

    static void TestCapacity()
    {
        std::forward_list<int> nFlist{1, 2, 3, 4, 5, 6};

        // forward_list 没有 size() 成员函数！为了节省内存，其大小需要 O(n) 时间计算。
        // std::cout << "The forward_list's size:" << nFlist.size() << std::endl; // 错误：无此成员

        // 如果需要获取大小，必须使用 std::distance 遍历计算（性能开销大）
        size_t nCount = std::distance(nFlist.begin(), nFlist.end());
        std::cout << "The forward_list's size (computed): " << nCount << std::endl;

        nFlist.push_front(0); // 在头部插入
        // nFlist.push_back(7); // 错误：没有 push_back，因为是单向链表

        // 判断容器是否为空是高效的 O(1)，因为有独立的头节点
        std::cout << "Container is empty: " << nFlist.empty() << std::endl;

        // forward_list 没有 shrink_to_fit() 和 reserve() 成员函数。
        // 内存管理由链表节点自身控制。
        // 获取其最大可能大小（理论值，通常很大）
        std::cout << "Max possible size: " << nFlist.max_size() << std::endl;
    }

    static void TestCRUD()
    {
        {
            // 介绍增加操作
            std::forward_list<int> nFlist{2, 3, 4}; // 构造后：head -> 2 -> 3 -> 4

            // 仅在头部插入非常高效 O(1)
            nFlist.push_front(1); // 头部插入后：head -> 1 -> 2 -> 3 -> 4

            std::forward_list<Person> perFlist;
            perFlist.push_front(Person("Eve", 21)); // 头部构造临时对象再移动
            perFlist.emplace_front("Mario", 25); // 在头部就地构造，效率更高

            // 在其他位置插入，需要使用 insert_after 或 emplace_after
            // 要插入一个元素，你需要指向它【前一个位置】的迭代器
            auto it = nFlist.begin(); // 获取指向第一个元素（1）的迭代器
            nFlist.insert_after(it, 99); // 在第一个元素【之后】插入99。链表变为：head -> 1 -> 99 -> 2 -> 3 -> 4
            nFlist.emplace_after(it, 88); // 在第一个元素【之后】就地构造插入88。链表变为：head -> 1 -> 88 -> 99 -> 2 -> 3 -> 4

            // 在序列末尾插入需要先找到最后一个元素（O(n)操作）
            auto before_end = nFlist.before_begin();
            for (auto& _ : nFlist)
            {
                // 循环次数为 size()
                ++before_end; // 最终 before_end 指向最后一个元素
            }
            nFlist.insert_after(before_end, 777); // 在最后一个元素后插入
        }

        {
            // 介绍删除操作
            std::forward_list<int> nFlist{0, 1, 2, 3, 4, 5, 3, 6};
            nFlist.pop_front(); // 删除头部元素，高效 O(1)

            // 删除特定位置的元素，需要使用 erase_after
            // 要删除一个元素，你需要指向它【前一个位置】的迭代器
            auto it = nFlist.before_begin(); // 获取头节点（第一个元素之前的“位置”）
            ++it; // 现在 it 指向第一个元素（1）的前一个位置（即头节点）
            nFlist.erase_after(it); // 删除 it（头节点）【之后】的元素，即删除第一个元素（1）

            // 删除所有值等于特定值的元素 O(n)
            nFlist.remove(3);
            // 删除所有满足条件的元素
            nFlist.remove_if([](int n) { return n % 2 == 0; });

            nFlist.clear(); // 清除所有元素
        }

        {
            // 介绍查操作
            std::forward_list<int> nFlist{1, 2, 3, 4, 5, 5, 6, 6};

            // forward_list 不支持随机访问，没有 operator[], at(), front(), back() 成员函数。
            // 访问首元素是高效的 O(1)
            std::cout << "The first element is: " << *nFlist.begin() << std::endl;

            // 访问其他元素需要遍历，时间复杂度为 O(n)
            // 查找元素需要使用算法，例如 std::find
            auto found_it = std::find(nFlist.begin(), nFlist.end(), 4);
            if (found_it != nFlist.end())
            {
                std::cout << "Found element: " << *found_it << std::endl;
            }
        }

        {
            // 介绍修改的操作
            std::forward_list<int> nFlist{1, 2, 3, 4, 5, 6, 7, 8};

            // 修改元素必须通过迭代器
            auto it = nFlist.begin();
            *it = 99; // 修改第一个元素的值
            std::advance(it, 2); // 将迭代器向前移动2位（现在指向第三个元素）
            *it = 33; // 修改第三个元素的值

            // 范围 for 循环修改是安全且常用的方式
            for (int& elem : nFlist)
            {
                if (elem > 3 && elem < 7)
                {
                    elem *= 2;
                }
            }
        }
    }
};
#endif //CONTAINER_TESTFORWARD_LIST_H
